\section{Файл с индексами в программе \IT{fortune}}

(Эта часть впервые появилась в моем блоге 25 апреля 2015.)

\IT{fortune} это хорошо известная программа в UNIX, которая показывает случайную фразу из коллекции.
Некоторые гики настраивают свою систему так, что \IT{fortune} запускается после входа в систему.
\IT{fortune} берет фразы из текстовых файлов расположенных в \IT{/usr/share/games/fortunes} (по крайней мере, в Ubuntu Linux).
Вот пример (текстовый файл \q{fortunes}):

\begin{lstlisting}
A day for firm decisions!!!!!  Or is it?
%
A few hours grace before the madness begins again.
%
A gift of a flower will soon be made to you.
%
A long-forgotten loved one will appear soon.

Buy the negatives at any price.
%
A tall, dark stranger will have more fun than you.
%
...
\end{lstlisting}

Так что это фразы, иногда из нескольких строк, все разделены знаком процента.
Задача программы \IT{fortune} это найти случайную фразу и вывести её.
Чтобы это сделать, она должна просканировать весь текстовый файл, подсчитать кол-во фраз, выбрать случайную и вывести.
Но текстовый файл может стать большим, и даже на современных компьютерах, этот наивный алгоритм немного неэкономичный
по отношению к ресурсам.
Прямолинейный метод это держать бинарный файл с индексами, содержащий смешение каждой фразы в текстовом файле.
С файлом индексов, программа \IT{fortune} может работать намного быстрее: просто выбрать случайный элемент из индекса,
взять смещение оттуда, найти смещение в текстовом файле и прочитать фразу оттуда.
Это и сделано в программе \IT{fortune}.
Посмотрим, что внутри файла с индексами (это .dat-файлы в том же директории) в шестнадцатеричном редакторе.
Конечно, эта программа с открытыми исходными кодами, но сознательно, мы не будем подсматривать в исходники.

\lstinputlisting{ff/fortune/1.lst}

Без всякой посторонней помощи, мы видим что здесь 4 4-батных элемента в каждой 16-байтной строке.
Вероятно, это и есть наш массив с индексами.
Попробую загрузить весь файл в Wolfram Mathematica как массив из 32-битных целочисленных значений:

\begin{lstlisting}[style=custommath]
In[]:= BinaryReadList["c:/tmp1/fortunes.dat", "UnsignedInteger32"]

Out[]= {33554432, 2936078336, 3137339392, 251658240, 0, 37, 0, \
721420288, 1610612736, 2399141888, 3741319168, 335609856, 1208025088, \
2080440320, 2868969472, 3858825216, 537001984, 989986816, 2046951424, \
3305242624, 67305472, 1023606784, 1745027072, 2801991680, 3775070208, \
419692544, 755236864, 2130968576, 2902720512, 3573809152, 84213760, \
990183424, 1678049280, 2181365760, 2902786048, 3456434176, \
4144300032, 470155264, 1627783168, 2047213568, 3506831360, 168230912, \
1392967680, 2584150016, 4161208320, 654835712, 1493696512, \
2332557312, 2684878848, 3288858624, 3775397888, 4178051072, \
...
\end{lstlisting}

Нет, что-то не так. Числа подозрительно большие.
Вернемся к выводу \IT{od}: каждый 4-байтных элемент содержит 2 нулевых байта и 2 ненулевых байта,
так что смещения (по крайней мере в начале файла) как минимум 16-битные.
Вероятно, в этом файле используется другой \IT{endianness} (порядок байт)?
Порядок байт в Mathematica, по умолчанию, это \IT{little-endian}, как тот, что используется в Intel CPU.
Теперь я переключаю на \IT{big-endian}:

\begin{lstlisting}[style=custommath]
In[]:= BinaryReadList["c:/tmp1/fortunes.dat", "UnsignedInteger32", 
 ByteOrdering -> 1]

Out[]= {2, 431, 187, 15, 0, 620756992, 0, 43, 96, 143, 223, 276, \
328, 380, 427, 486, 544, 571, 634, 709, 772, 829, 872, 935, 993, \
1049, 1069, 1151, 1197, 1237, 1285, 1339, 1380, 1410, 1453, 1486, \
1527, 1564, 1633, 1658, 1745, 1802, 1875, 1946, 2040, 2087, 2137, \
2187, 2208, 2244, 2273, 2297, 2343, 2371, 2425, 2467, 2531, 2581, \
2637, 2654, 2698, 2726, 2751, 2799, 2840, 2883, 2913, 2958, 3023, \
3066, 3131, 3174, 3205, 3257, 3282, 3330, 3387, 3431, 3500, 3552, \
...
\end{lstlisting}

Теперь это можно читать.
Я выбрал случайный элемент (3066), а это 0xBFA в шестнадцатеричном виде.
Открываю текстовый файл 'fortunes' в шестнадцатеричном редакторе, выставляю 0xBFA как смещение, и вижу эту фразу:

\lstinputlisting{ff/fortune/2.lst}

Или:

\begin{lstlisting}
Do what comes naturally.  Seethe and fume and throw a tantrum.
%
\end{lstlisting}

Другие смещения тоже можно проверить и, да, они верные.

В Mathematica я также могу удостоверится, что каждый следующий элемент больше предыдущего.
Т.е., элементы возврастают.
На математическом жаргоне, это называется \IT{строго возрастающая монотонная ф-ция}.

\begin{lstlisting}[style=custommath]
In[]:= Differences[input]

Out[]= {429, -244, -172, -15, 620756992, -620756992, 43, 53, 47, \
80, 53, 52, 52, 47, 59, 58, 27, 63, 75, 63, 57, 43, 63, 58, 56, 20, \
82, 46, 40, 48, 54, 41, 30, 43, 33, 41, 37, 69, 25, 87, 57, 73, 71, \
94, 47, 50, 50, 21, 36, 29, 24, 46, 28, 54, 42, 64, 50, 56, 17, 44, \
28, 25, 48, 41, 43, 30, 45, 65, 43, 65, 43, 31, 52, 25, 48, 57, 44, \
69, 52, 62, 73, 62, 53, 37, 68, 71, 50, 41, 57, 69, 58, 70, 45, 54, \
38, 45, 50, 42, 61, 47, 43, 62, 189, 61, 56, 30, 85, 63, 48, 61, 58, \
81, 50, 55, 63, 83, 80, 49, 42, 94, 54, 67, 81, 52, 57, 68, 43, 28, \
120, 64, 53, 81, 33, 82, 88, 29, 61, 32, 75, 63, 70, 47, 101, 60, 79, \
33, 48, 65, 35, 59, 47, 55, 22, 43, 35, 102, 53, 80, 65, 45, 31, 29, \
69, 32, 25, 38, 34, 35, 49, 59, 39, 41, 18, 43, 41, 83, 37, 31, 34, \
59, 72, 72, 81, 77, 53, 53, 50, 51, 45, 53, 39, 70, 54, 103, 33, 70, \
51, 95, 67, 54, 55, 65, 61, 54, 54, 53, 45, 100, 63, 48, 65, 71, 23, \
28, 43, 51, 61, 101, 65, 39, 78, 66, 43, 36, 56, 40, 67, 92, 65, 61, \
31, 45, 52, 94, 82, 82, 91, 46, 76, 55, 19, 58, 68, 41, 75, 30, 67, \
92, 54, 52, 108, 60, 56, 76, 41, 79, 54, 65, 74, 112, 76, 47, 53, 61, \
66, 53, 28, 41, 81, 75, 69, 89, 63, 60, 18, 18, 50, 79, 92, 37, 63, \
88, 52, 81, 60, 80, 26, 46, 80, 64, 78, 70, 75, 46, 91, 22, 63, 46, \
34, 81, 75, 59, 62, 66, 74, 76, 111, 55, 73, 40, 61, 55, 38, 56, 47, \
78, 81, 62, 37, 41, 60, 68, 40, 33, 54, 34, 41, 36, 49, 44, 68, 51, \
50, 52, 36, 53, 66, 46, 41, 45, 51, 44, 44, 33, 72, 40, 71, 57, 55, \
39, 66, 40, 56, 68, 43, 88, 78, 30, 54, 64, 36, 55, 35, 88, 45, 56, \
76, 61, 66, 29, 76, 53, 96, 36, 46, 54, 28, 51, 82, 53, 60, 77, 21, \
84, 53, 43, 104, 85, 50, 47, 39, 66, 78, 81, 94, 70, 49, 67, 61, 37, \
51, 91, 99, 58, 51, 49, 46, 68, 72, 40, 56, 63, 65, 41, 62, 47, 41, \
43, 30, 43, 67, 78, 80, 101, 61, 73, 70, 41, 82, 69, 45, 65, 38, 41, \
57, 82, 66}
\end{lstlisting}

Как мы видим, за исключением только первых 6-и значений
(которые, вероятно, относятся к заголову файла с индексами),
все числа на самом деле это длины текстовых строк
(смещение следующей фразы минус смещение текущей фразы на самом деле это длина текущей фразы).

Важно помнить, что порядок байт (\IT{endiannes}) легко спутать с неверным началом массива.
Действительно, из вывода \IT{od} мы можем увидеть что каждый элемент начинается с двух нулей.
Но если сдвинуть на два байта в любую сторону, массив можно интерпретировать как \IT{little-endian}:

\lstinputlisting{ff/fortune/3.lst}

Если будем интерпретировать массив как \IT{little-endian}, то первый элемент это 0x4801, второй 0x7C01, итд.
Старшая 8-битная часть каждого из этих 16-битных значений, выглядит для нас как случайная, а младшая 8-битная часть
возрастает.

Но я уверен, что это массив \IT{big-endian}, потому что самый последний 32-битных элемент в файле
тоже \IT{big-endian} (и это \IT{00 00 5f c4}):

\lstinputlisting{ff/fortune/4.lst}

Возможно, разработчик программы \IT{fortune} имел big-endian-компьютер, а может программа была портирована с чего-то такого.

ОК, массив big-endian, и, если пользоваться здравым смыслом, самая первая фраза в текстовом файле должна начинается с нулевого
смещения.
Так что нулевое значение должно присутствовать где-то в самом начале.
У нас в начале пара нулевых элементов. Но второй выглядит более привлекательно: после него идет 43, и 43 это корректное
смещение, по которому в текстом файле находится фраза на английском.

Последний элемент массива это 0x5FC4, а в текстовом файле нет байта по этому смещению.
Так что последний элемент указывает на место сразу за концом файла.
Вероятно так сделано, потому что длина фразы вычисляется как разница между смещением текущей фразы
и смещением следующей фразы.
Это может быть быстрее, чем искать в строке символ процента. 
Но это не будет работать для последнего элемента.
Так что элемент-\IT{пустышка} добавлен в конец массива.

Так что первые 5 32-битных значений, видимо, это что-то вроде заголовка.

О, и я забыл подсчитать количество фраз в текстовом файле:

\lstinputlisting{ff/fortune/5.lst}

Количество фраз может присутствовать в индексе, а может и нет.
В случае с простейшими файлами индексов, количество элементов легко получить из размера файла.
Так или иначе, в этом текстовом файле 432 фразы.
И мы видим что-то очень знакомое во втором элементе (значение 431).
Я проверил остальные файлы (literature.dat и riddles.dat в Ubuntu Linux), и да, второй 32-битный элемент это
количество фраз минус 1.
А почему \IT{минус 1}? Вероятно, это не количество фраз, а скорее номер последней фразы (считая с нуля)?

В заголовке есть еще и другие элементы.
В Mathematica, я загружаю каждый из трех доступных файлов и смотрю на заголовок:

\begin{figure}[H]
\centering
\myincludegraphics{ff/fortune/mathematica.png}
\end{figure}

Не знаю, что могут означать другие значения, кроме размера файла с индексами.
Некоторые поля одинаковые для всех файлов, некоторые нет.
Судя по моему опыту, тут могут быть:

\begin{itemize}
\item сигнатура фалйа;
\item верия файла;
\item контрольная сумма;
\item какие-нибудь флаги;
\item может быть даже идентификатор языка;
\item дата/время текстового фалйа, так что программа \IT{fortune} будет регенирировать файл с индексами только тогда, когда
пользователь изменит текстовый файл.
\end{itemize}

Например, .SYM-файлы в Oracle (\myref{Oracle_SYM_files_example}), содержащие таблицу символов DLL-файлов,
также содержат дату/время соответствующей DLL, чтобы быть уверенным, что файл всё еще верен.

Но с другой стороны, дата/время и текстового файла и файла с индексами легко может испортится после
архифирования/разархивирования/инсталлирования/развертывания/итд.

По моему мнению, здесь нет даты/времени. Самый компактный способ представления даты и времени это UNIX-время,
а это большое 32-битное число. Ничего такого мы здесь не видим. Другие способы представления даже еще менее компактны.

Вот вероятный алгоритм, как работает \IT{fortune}:

\begin{itemize}
\item прочитать номер последней фразы из второго элемента;
\item сгенерировать случайное число в пределах 0..номер\_последней\_фразы;
\item найти соответствующий элемент в массиве смещений, также прочитать следующее смещение;
\item вывести в \IT{stdout} все символы из текстового файла начиная со смещения до следующего смещения минус 2 (чтобы
проигнорировать терминирующий знак процента и символ из следующей фразы).
\end{itemize}

\subsection{Хакинг}

Проверим некоторые из наших предположений.
Я создам текстовый файл по такому пути и с таким именем: \IT{/usr/share/games/fortunes/fortunes}:

\begin{lstlisting}
Phrase one.
%
Phrase two.
%
\end{lstlisting}

Теперь такой файл fortunes.dat. Я взял заголовок из оригинального fortunes.dat, я поменял второе поле
(количество фраз) в 0 и я оставил два элемент в массиве:
0 and 0x1c, потому что длина всего текста в файле \IT{fortunes} это 28 (0x1c) байт:

\lstinputlisting{ff/fortune/6.lst}

Запускаю:

\lstinputlisting{ff/fortune/7.lst}

Что-то не так. Поменяем второе поле на 1:

\lstinputlisting{ff/fortune/8.lst}

Теперь работает. Показывает только первую фразу:

\lstinputlisting{ff/fortune/9.lst}

Хммм. Оставим только один элемент в массиве (0) без заключающего:

\lstinputlisting{ff/fortune/10.lst}

Программа fortune всегда показывает только первую фразу.

Из этого эксперимента мы узнали что знак процента из текстового файла все-таки обрабатывается, а размер вычисляется
не так, как предполагал, вероятно, последний элемент массива не используется.
Хотя, его все еще можно использовать. И возможно он использовался в прошлом?

% TODO second phrase!

\subsection{Файлы}

Ради демонстрации, я не смотрел в исходный код \IT{fortune}.
Если и вы хотите попытаться понять смысл других значений в заголовке файла с индексами, вы тоже можете попытаться
достичь этого без заглядывания в исходники.
Файлы, которые я взял из Ubuntu Linux 14.04, находятся здесь: \url{http://beginners.re/examples/fortune/}, похаканные
файлы там же.

И еще я взял файлы из 64-битной Ubuntu, но элементы массива все так же 32-битные.
Вероятно потому что текстовые файлы \IT{fortune} никогда не превышают размер в 4\ac{GiB}.
Но если бы превышали, все элементы должны были бы иметь ширину в 64 бита, чтобы хранить смещение в текстовом файле
размером больше чем 4GiB.

Для нетерпеливых читателей, исходники \IT{fortune} здесь:
\url{https://launchpad.net/ubuntu/+source/fortune-mod/1:1.99.1-3.1ubuntu4}.

